package leetcode.code0390;

import leetcode.IDebug;

public class Solution2 implements IDebug {

	public int lastRemaining(int n) {
		int start = 1;
		int round = 1;// 第一轮消除
		while (n > 1) {
			if (round % 2 == 1) { // 正向
				start += (int) Math.pow(2, round - 1);// 第一个数被消除，第二个数被保留
			} else { // 反向
				// 剩下偶数个数反向第一个被保留比如2,4,6,8中2留下了。
				// 剩下奇数个数反向第二个被保留比如2,4,6,8,10中4留下了。
				start += (n % 2 == 0) ? 0 : (int) Math.pow(2, round - 1);
			}
			round++;
			n >>= 1;// 数量减半
		}
		return start;
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
